/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-06-05
 * Time: 20:14
 */
//最小覆盖字串 滑动窗口
public class Solution {
    public String minWindow(String ss, String tt) {

        int[] hash1 = new int[128];//存放ss的元素个数
        int[] hash2 = new int[128];//存放tt元素的个数

        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int kinds = 0;//统计tt中字符的种类
        for (char x : t) {
            if (hash2[x]++ == 0) {
                kinds++;
            }
        }

        int minLen = Integer.MAX_VALUE;//结果的最小长度
        int begin = -1;//最小结果的左边界
        for (int left = 0, right = 0, count = 0; right < ss.length(); right++) {
            char in =  s[right];//进窗口
            if (++hash1[in] == hash2[in]) {
                count++;//维护count(count记录ss中有效字符的种类(个数一致才有效))
            }

            while (count == kinds) {//判断
                if (right - left + 1 < minLen) {//更新结果
                    begin = left;
                    minLen = right - left + 1;
                }

                char out = s[left++];
                if (hash1[out]-- == hash2[out]) {//出窗口
                    count--;
                }
            }
        }
        return begin == -1 ? new String() : ss.substring(begin, begin + minLen);
    }
}
